package 力扣_树算法.搜索树;


/**235. 二叉搜索树的最近公共祖先
 * @author zx
 * @create 2022-04-16 9:11
 */
public class Num235 {
    /**
     从根节点开始遍历:
     如果当前节点的值大于 p 和 q 的值,说明 p 和 q 应该在当前节点的左子树,因此将当前节点移动到它的左子节点;
     如果当前节点的值小于 p 和 q 的值,说明 p 和 q 应该在当前节点的右子树,因此将当前节点移动到它的右子节点;
     如果当前节点的值不满足上述两条要求,那么说明当前节点就是[分岔点].此时,p 和 q 要么在当前节点的不同的子树中
     要么其中一个就是当前节点。
     * @return 递归(自己写的)
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if((p.val >= root.val && q.val <= root.val) || (p.val <= root.val && q.val >= root.val)){
            return root;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }

    /**
     * @return 自己的做法
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val == p.val || root.val == q.val){
            return root;
        }
        if(p.val < root.val && q.val < root.val){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(p.val > root.val && q.val > root.val){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;
    }
}
